Surgical simulation requires interactive modeling and visualization of complex, 3D anatomical structures. For example, surgery of the abdomen involves probing and cutting through organs and tissues that have complex shapes and material properties. Because modeling the deformation and cutting of tissue requires a representation of interior structure, volumetric object representation is well suited to surgical simulation. A volumetric representation can incorporate detailed information about internal anatomical or physiological structure. This detailed information can be used to model tissue deformation more accurately than a model which represents the object surface and assumes a homogeneous interior. Because a volumetric representation uses the data produced by 3D medical scanners directly, errors that are introduced by fitting polygonal surfaces to the discrete image data can be avoided.
In a volumetric object representation, the object is stored as a discrete 3D array of sampled data elements. Each data element can consist of several bytes of information including visual properties, such as color or transparency, or material properties, such as tissue type or elasticity. The major disadvantage of volumetric representations is that objects can consist of millions of volume elements. This large data requirement poses challenges for memory storage and access, for real-time rendering and for physically realistic modeling of object interactions. There is therefore a need for a fast algorithm for modeling the deformation of volumetric objects. The algorithm should be able to model a range of materials including rigid, deformable, elastic, and plastic substances. In addition, the algorithm should model anisotropic materials, such as muscle, which have different material properties along different axes.
By way of background, there are three relevant basic technologies. These are: Volume Graphics; physics-based graphics; and soft tissue modeling using Finite Element Modeling (FEM) and other methods.
As described by A. Kaufman et al. in "Volume Graphics", IEEE, Computer, Vol. 23, 7, pp. 51-64, 1993; "Volume Visualization", CRC Handbook of Computer Science and Engineering, 1996; "Efficient algorithms for 3D scan-conversion of parametric curves, surfaces, and volumes", Computer Graphics, Vol. 21, 4, ppo. 171-179, 1987; and "Volume sampled elementization of geometric primitives", Proceedings Visualization '93, San Jose, Calif., pp. 78-84, October, 1993, there are various strategies to deal with the synthesis, modeling, manipulation, and rendering of volumetric objects. Prior work in Volume Graphics includes the development of techniques to replace the traditional graphics pipeline of polygon graphics with new methods for volumetric data. For example, shading, antialiasing, and rendering algorithms, described by Kaufman in Volume Visualization, IEEE Computer Society Press, Los Alamitos, Calif., 1991, are replaced by their volumetric counterparts. This is also discussed by L. Sobierajski and A. Kaufman in "Volumetric ray tracing", proc. Volume Visualization Symposium, Washington, D.C., pp. 11-18, 1994; and in the aforementioned October 1993 Proceedings Visualization reference.
New algorithms and hardware implementations for volume rendering of regular volumes are described by H. Pfister in his Ph.D. thesis, SUNY at Stony Brook, August 1996; P. Lacroutte and M. Levoy, "Fast volume rendering using a shearwarp factorization of the viewing transform", proc. SIGGRAPH, Computer Graphics, pp. 451-457, 1994; and G. Knittle in "A scalable architecture for volume rendering", Computer and Graphics, Vol. 19, No. 5, pp. 653-665, 1995. Recently, attention in Volume Graphics has been given to object manipulation, including haptic interaction with volumetric objects and physically realistic modeling of object interactions as discussed by S. Gibson, "Beyond Volume Rendering, Visualization, Haptic Exploration, and Physical Modeling of Voxel-Based Objects" in Visualization in Scientific Computing, eds. R. Scatini, J. Van Wijk, and P. Zanarini Springer-Verlas, pp. 10-24, 1995 and by R. Avila, , L. Sobieraajski in "A Haptic Interaction Method for Volume Visualization", Proc. Visualization '96, pp. 197-204, 1996.
There is also a growing interest in physically realistic modeling of object interaction in the graphics community. This includes both detecting object collisions and modeling the energy and momentum transfer between colliding objects, problems that have been addressed for real-time interactions of rigid object representations. See B. Mirtich, J. Canny, "Impulse-based simulation of rigid bodies", proc. 1995 Workshop on Interactive 3D Graphics, pp. 181-188, April, 1995; D. Baraff, "Analytical methods for dynamic simulation of non-penetrating rigid bodies", (proc. SIGGRAPH), Computer Graphics, Vol. 24, pp. 19-28, 1989 and the above Gibson article.
As to soft-tissue modeling, finite Element Modeling (FEM) can be used to model complex materials. Careful selection of element nodes and accurate knowledge of the material properties at each node point enables accurate simulation of complex mechanical behaviors. FEM has been applied to modeling the skin and muscle layers of the face as described by D. Terzopoulos, J. Platt, A. Barr, K. Fleischer in "Elastically deformable models", Computer Graphics, Vol 21, 4, pp. 205-214, July, 1987; D. Terzopoulos, K. Waters, "Physically-based facial modeling, analysis, and animation", J. Visualization and Computer Animation, Vol. 1, pp. 73-80, 1990; and Y. Lee, D. Terzopoulos and K. Waters, "Realistic modeling for facial animation", Computer Graphics (proc. SIGGRAPH), pp. 55-62, 1995. Skeletal muscle modeling is described in D. Chen, "Pump it up; computer animation of a biomechanically based model of muscle using the finite element method", PhD thesis, Media Arts and Sciences, MIT, 1991. Moreover, modeling of the liver is described by Cotin et al. Biomed Vis '96 and modeling of the eye is described by I. Hunter, T. Doukoglou, S. Lafontaine, and P. Charette in "A teleoperated microsurgical robot and associated virtual environment for eye surgery", Presence, Vol. 2, pp. 265-280, 1993.
However, because of computational requirements, FEM cannot be used in interactive applications unless the number of node points is small. Useful FEM computation reduction techniques such as multigrid methods and model analysis are described in A. Pentland, J. Williams, "Good Vibrations: modal dynamics for graphics and animation", Computer Graphics, Vol. 23, 3, pp. 215-222, July, 1989. Moreover, related techniques are described by I. Essa, S. Scarloff, A. Pentland, "Physically-based modeling for graphics and vision", in Directions in Geometric Computing, ed. Ralph Martin, "Information Geometers", U.K., 1993; and D. Metaxas, D. Terzopoulos, "Dynamic deformation of solid primitives with constraints", Computer Graphics (proc. SIGGRAPH), Vol. 26, 2, pp. 309-312, 1992. However, the computational complexity of FEM remains a bottleneck for interactive soft tissue modeling.
Other techniques that have been used to model soft tissue include: free-form deformation as described by T. Sedeberg and S. Parry in "Free-form Deformation of Solid Geometric Models", Computer Graphics (proc. SIGGRAPH) Vol. 22, 4, August 1986, pp. 151-160 and W. Hsu, J. Hughes, H. Kaufman, "Direct Manipulation of Free-form Deformations", Computer Graphics (proc. SIGGRAPH), Vol. 26, 2, pp. 177-184, 1992. Modeling of active surfaces are described by S. Cover, N. Ezquerra, J. O'Brien, R. Rowe, T. Gadacz, E. Palm in "Interactively deformable models for surgery simulation", IEEE Computer Graphics and Applications, Vol. 13, 6, pp. 68-75, 1993; whereas modeling for active cubes is described by M. Bro-Nielsen in "Modeling elasticity in solids using active cubes--application to simulated operations", in Computer Vision, Virtual Reality and Robotics in Medicine proc. CVRMed '95 ed. Nicholas Ayache, pp. 535-541.
Using a "zone of influence" to predefine the effect that displacement of a given node point will have on neighboring nodes is described by K. Waters in "A Muscle model for animating three-dimensional facial expression", Computer Graphics, Vol. 21, 4, pp. 17-24, July, 1987. Moreover, using implicit surfaces to model soft substances is described by M. Desbrun, M. P. Gascuel in "Animating soft substances with implicit surfaces", Computer Graphics (proc. SIGGRAPH), pp. 287-290, 1995. These techniques are useful because of their speed but their accuracy is limited for complex tissues.
By way of summary in object deformation, the large number of elements in a volumetric object poses a significant challenge for interactive applications that model physically realistic object deformation. One approach is to perform FEM calculations on a lower resolution grid. However, this does not take advantage of the high resolution data produced by medical scanners. Thus, presently there is no computationally efficient way to deform volumetric objects.